//求二叉树的最小深度：叶子结点是左右孩子都没有，而不是只有一个孩子
//使用递归或层序遍历的方法
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
};
#include <algorithm>
using std::min;
//递归
//跟求最大深度有些不同，因为只有检测到没有孩子才算叶子结点
int getDepth(TreeNode* node){
    if(!node) return 0;
    //只有一个孩子，则返回孩子的getDepth（）深度
    if(!node->left&&node->right) return 1+getDepth(node->right);
    if(!node->right&&node->left) return 1+getDepth(node->left);

    //最后返回左右子树最小深度的最小值
    return 1+min(getDepth(node->right),getDepth(node->left));
}
int minDepth_recursion (TreeNode* root){
    if(!root) return 0;
    return getDepth(root);
}

#include <queue>
using std::queue;
//迭代法，使用队列
//本质上还是使用层序遍历，当有节点没有孩子时返回的深度就是最小深度
int minDepth_queue(TreeNode *root)
{
    if(!root) return 0;
    queue<TreeNode*> que;
    que.push(root);
    int depth=0;
    while(!que.empty()){
        int size=que.size();
        depth++;
        for(int i=0;i<size;i++){
            TreeNode* node=que.front();
            que.pop();
            if(node->left) que.push(node->left);
            if(node->right) que.push(node->right);
            //找到叶子节点，返回深度就是最小深度
            if(!node->left&&!node->right) return depth;
        }
    }
    return 0;//这个返回什么都行，最终都是在循环寻找叶子节点时返回，这个返回语句不会调用
}